#define _CRT_SECURE_NO_WARNINGS 1
typedef pair<int, int> PII;

struct DListNode {
    int val;
    int key;
    DListNode* next;
    DListNode* pre;
    DListNode() :next(nullptr), pre(nullptr), key(0), val(0) {};
    DListNode(const int _k, const int _v) :next(nullptr), pre(nullptr), key(_k), val(_v) {};
};
class LRUCache {
public:
    typedef DListNode node;

    void insert(node* newnode) {
        newnode->next = head->next;
        head->next->pre = newnode;

        newnode->pre = head;
        head->next = newnode;
    }

    void erase(node* node) {
        node->next->pre = node->pre;
        node->pre->next = node->next;
        node->next = nullptr;
        node->pre = nullptr;
    }
    LRUCache(int capacity) {
        cap = capacity;
        sz = 0;
        head = new DListNode();
        tail = new DListNode();
        head->next = tail;
        head->pre = tail;
        tail->pre = head;
        tail->next = head;
    }

    int get(int key) {
        if (mp[key]) {
            node* t = mp[key];
            erase(t);
            insert(t);
            return mp[key]->val;
        }
        return -1;
    }

    void put(int key, int value) {
        if (mp[key]) {
            node* t = mp[key];
            mp[key]->val = value;
            erase(t);
            insert(t);
            return;
        }
        if (sz == cap) {
            node* t = tail->pre;
            cout << t->key << endl;
            mp[t->key] = nullptr;
            t->pre->next = tail;
            tail->pre = t->pre;
            delete t;
            sz--;
        }
        node* newnode = new DListNode(key, value);
        newnode->next = head->next;
        head->next->pre = newnode;
        newnode->pre = head;
        head->next = newnode;
        mp[key] = newnode;
        sz++;
    }
    unordered_map<int, node*> mp;
    node* head;
    node* tail;
    int cap;
    int sz;
};

